// 分析斐波那契数列递推公式递归版本的问题，试着为该函数提供一个Cache，使其计算效率提升
package main

import (
	"fmt"
	"time"
)

// 无优化版本
func fibonacciNoCache(n int) uint64 {
	if n <= 0 {
		fmt.Println("n > 0")
	} else if n == 1 {
		return 1
	} else if n == 2 {
		return 1
	}
	return fibonacciNoCache(n-1) + fibonacciNoCache(n-2)
}
func outputFibonacciNoCache(n int) {
	output := make([]uint64, 0, n)
	start := time.Now().UnixMicro()
	for i := 1; i < n; i++ {
		output = append(output, fibonacciNoCache(i))
	}
	ending := time.Now().UnixMicro()
	fmt.Println(output)
	fmt.Printf("耗时%d微秒\n", (ending - start))
}

var fibonacciCacheMap = map[int]uint64{
	1: 1, 2: 1,
}

// Cache优化版本
func fibonacciCache(n int) uint64 {
	if fib, ok := fibonacciCacheMap[n]; ok {
		return fib
	}
	fibonacciCacheMap[n] = fibonacciCacheMap[n-1] + fibonacciCacheMap[n-2]
	return fibonacciCacheMap[n]
}
func outputFibonacciCache(n int) {
	output := make([]uint64, 0, n)
	start := time.Now().UnixMicro()
	for i := 1; i < n; i++ {
		output = append(output, fibonacciCache(i))
	}
	ending := time.Now().UnixMicro()
	fmt.Println(output)
	fmt.Printf("耗时%d微秒\n", (ending - start))
}

func main() {
	// 无优化版本
	outputFibonacciNoCache(40)
	// Cache优化版本
	outputFibonacciCache(40)

}
